#
# @lc app=leetcode.cn id=15 lang=python3
#
# [15] 三数之和
#

"""
本题可转换为两数之和问题，使 nums[j] + nums[k] = -nums[i]，并且为了方便使用双指针，对 nums 先进行排序
为使答案中不存在重复的三元组：
  在外层循环中，如果 nums[i] = nums[i-1]，则找到的 j, k 也相同，所以可以跳过该值继续循环
  在内层循环中也是同样的，当找到符合条件的 i, j, k 以后，查找 j 的后一位是否与之相同，相同则跳过该值继续循环

优化：
  在枚举 i 的过程中，
  当 nums[i] + nums[j] + nums[k] > 0 时，表明最小的三个数之和大于 0 ，后续的值将更大，不存在三数之和等于0的情况，直接跳出循环，返回空列表
  当 nums[i] + nums[-2] + nums[-1] < 0 时，表明最大的两个数与 nums[i] 相加也小于 0 ，说明当前的 nums[i] 不存在答案（负数过大，需要向右寻找较小的负数），跳过本次循环进入下一次循环
"""


# @lc code=start
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        n = len(nums)
        nums.sort()
        res = []
        
        for i in range(n-2):
            x = nums[i]
            if i > 0 and x == nums[i-1]:continue
            if x + nums[i+1] + nums[i+2] > 0:break
            if x + nums[-2] + nums[-1] < 0:continue

            j = i + 1
            k = n - 1
            while j < k:
                s = x + nums[j] + nums[k]
                if s > 0: k -= 1
                elif s < 0: j += 1
                else:
                    res.append([x, nums[j], nums[k]])
                    j += 1
                    while j < k and nums[j] == nums[j-1]:j += 1
                    k -= 1
                    while k > j and nums[k] == nums[k+1]:k -= 1

        return res


                    



# @lc code=end

